<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>深度-广度搜索-状态空间-cnblog | 凌歆的博客</title>
    <meta name="generator" content="VuePress 1.9.5">
    <link rel="icon" href="/img/favicon.ico">
    <meta name="description" content="web前端技术博客,专注web前端学习与总结。JavaScript,js,ES6,TypeScript,vue,React,python,css3,html5,Node,git,github等技术文章。">
    <meta name="keywords" content="前端博客,个人技术博客,前端,前端开发,前端框架,web前端,前端面试题,技术文档,学习,面试,JavaScript,js,ES6,TypeScript,vue,python,css3,html5,Node,git,github,markdown">
    <meta name="baidu-site-verification" content="7F55weZDDc">
    <meta name="theme-color" content="#11a8cd">
    
    <link rel="preload" href="/assets/css/0.styles.d9c8cf8c.css" as="style"><link rel="preload" href="/assets/js/app.57550e13.js" as="script"><link rel="preload" href="/assets/js/2.f014c35f.js" as="script"><link rel="preload" href="/assets/js/111.b092af6d.js" as="script"><link rel="prefetch" href="/assets/js/10.03a98811.js"><link rel="prefetch" href="/assets/js/100.145e708e.js"><link rel="prefetch" href="/assets/js/101.098ca5c8.js"><link rel="prefetch" href="/assets/js/102.4d45c69a.js"><link rel="prefetch" href="/assets/js/103.499de505.js"><link rel="prefetch" href="/assets/js/104.c2c1b9b6.js"><link rel="prefetch" href="/assets/js/105.4e9b0663.js"><link rel="prefetch" href="/assets/js/106.9bb8cf6f.js"><link rel="prefetch" href="/assets/js/107.a81b32d7.js"><link rel="prefetch" href="/assets/js/108.81511e67.js"><link rel="prefetch" href="/assets/js/109.6a6741bf.js"><link rel="prefetch" href="/assets/js/11.e8729182.js"><link rel="prefetch" href="/assets/js/110.de657fe7.js"><link rel="prefetch" href="/assets/js/112.2dca5709.js"><link rel="prefetch" href="/assets/js/113.dbed1fac.js"><link rel="prefetch" href="/assets/js/114.e95a0131.js"><link rel="prefetch" href="/assets/js/115.2e3e8285.js"><link rel="prefetch" href="/assets/js/116.e64f7fec.js"><link rel="prefetch" href="/assets/js/117.583552c9.js"><link rel="prefetch" href="/assets/js/118.aa5d18f0.js"><link rel="prefetch" href="/assets/js/119.0c7b52d7.js"><link rel="prefetch" href="/assets/js/12.d63acec2.js"><link rel="prefetch" href="/assets/js/120.13f86281.js"><link rel="prefetch" href="/assets/js/121.e2b5b7f9.js"><link rel="prefetch" href="/assets/js/122.5252216a.js"><link rel="prefetch" href="/assets/js/123.8b8a3503.js"><link rel="prefetch" href="/assets/js/124.60df855c.js"><link rel="prefetch" href="/assets/js/125.f073ab1c.js"><link rel="prefetch" href="/assets/js/126.7b73de6a.js"><link rel="prefetch" href="/assets/js/127.4e25971c.js"><link rel="prefetch" href="/assets/js/128.0edf0e06.js"><link rel="prefetch" href="/assets/js/129.5cb5a70a.js"><link rel="prefetch" href="/assets/js/13.2259ef71.js"><link rel="prefetch" href="/assets/js/130.00247fda.js"><link rel="prefetch" href="/assets/js/131.d6fc003a.js"><link rel="prefetch" href="/assets/js/132.1a32b18f.js"><link rel="prefetch" href="/assets/js/133.e46c0193.js"><link rel="prefetch" href="/assets/js/134.a6ad681f.js"><link rel="prefetch" href="/assets/js/135.2fcbe137.js"><link rel="prefetch" href="/assets/js/136.f69bf451.js"><link rel="prefetch" href="/assets/js/137.b9ef2fcc.js"><link rel="prefetch" href="/assets/js/138.7fdd9feb.js"><link rel="prefetch" href="/assets/js/139.a3a37c91.js"><link rel="prefetch" href="/assets/js/14.0d6b23b9.js"><link rel="prefetch" href="/assets/js/140.a7c013ae.js"><link rel="prefetch" href="/assets/js/141.956c36ce.js"><link rel="prefetch" href="/assets/js/142.5aacfe42.js"><link rel="prefetch" href="/assets/js/143.57d691ef.js"><link rel="prefetch" href="/assets/js/144.b1e5766e.js"><link rel="prefetch" href="/assets/js/145.463284b7.js"><link rel="prefetch" href="/assets/js/146.6cc6420c.js"><link rel="prefetch" href="/assets/js/147.5b78c5a2.js"><link rel="prefetch" href="/assets/js/148.8d1d7679.js"><link rel="prefetch" href="/assets/js/149.4e0eb213.js"><link rel="prefetch" href="/assets/js/15.f6fde69d.js"><link rel="prefetch" href="/assets/js/150.b183de37.js"><link rel="prefetch" href="/assets/js/151.729ae770.js"><link rel="prefetch" href="/assets/js/152.b1297018.js"><link rel="prefetch" href="/assets/js/153.bb991bca.js"><link rel="prefetch" href="/assets/js/154.6f2286aa.js"><link rel="prefetch" href="/assets/js/155.6a9c7e4d.js"><link rel="prefetch" href="/assets/js/156.f7bd535d.js"><link rel="prefetch" href="/assets/js/157.64c0065c.js"><link rel="prefetch" href="/assets/js/158.d31ae949.js"><link rel="prefetch" href="/assets/js/159.7daea8a7.js"><link rel="prefetch" href="/assets/js/16.7be21beb.js"><link rel="prefetch" href="/assets/js/160.33cc971a.js"><link rel="prefetch" href="/assets/js/161.1676442a.js"><link rel="prefetch" href="/assets/js/162.71378046.js"><link rel="prefetch" href="/assets/js/163.99e49959.js"><link rel="prefetch" href="/assets/js/164.306f07d2.js"><link rel="prefetch" href="/assets/js/165.170977c7.js"><link rel="prefetch" href="/assets/js/166.f8602525.js"><link rel="prefetch" href="/assets/js/167.eea5c001.js"><link rel="prefetch" href="/assets/js/168.0146a311.js"><link rel="prefetch" href="/assets/js/169.05f9c9d9.js"><link rel="prefetch" href="/assets/js/17.2543f471.js"><link rel="prefetch" href="/assets/js/170.25d602b2.js"><link rel="prefetch" href="/assets/js/171.1ada26a6.js"><link rel="prefetch" href="/assets/js/172.2a0f697c.js"><link rel="prefetch" href="/assets/js/173.230d8ca8.js"><link rel="prefetch" href="/assets/js/174.e3758a2b.js"><link rel="prefetch" href="/assets/js/175.0f19f8ea.js"><link rel="prefetch" href="/assets/js/176.bf70d37d.js"><link rel="prefetch" href="/assets/js/177.4400f272.js"><link rel="prefetch" href="/assets/js/178.85af7b89.js"><link rel="prefetch" href="/assets/js/179.4cfaaaa2.js"><link rel="prefetch" href="/assets/js/18.394415f8.js"><link rel="prefetch" href="/assets/js/180.449c8409.js"><link rel="prefetch" href="/assets/js/181.73276924.js"><link rel="prefetch" href="/assets/js/182.5fab25cc.js"><link rel="prefetch" href="/assets/js/183.ecd4934d.js"><link rel="prefetch" href="/assets/js/184.246092cf.js"><link rel="prefetch" href="/assets/js/185.c671cd86.js"><link rel="prefetch" href="/assets/js/186.49bd1963.js"><link rel="prefetch" href="/assets/js/187.1fb32764.js"><link rel="prefetch" href="/assets/js/188.7c6885e9.js"><link rel="prefetch" href="/assets/js/189.a8701dec.js"><link rel="prefetch" href="/assets/js/19.ca7db8ea.js"><link rel="prefetch" href="/assets/js/190.ae3d3bde.js"><link rel="prefetch" href="/assets/js/191.ad7cd44e.js"><link rel="prefetch" href="/assets/js/192.bc443842.js"><link rel="prefetch" href="/assets/js/193.e4755764.js"><link rel="prefetch" href="/assets/js/194.814112ce.js"><link rel="prefetch" href="/assets/js/195.1c0aaa80.js"><link rel="prefetch" href="/assets/js/196.a6bd7add.js"><link rel="prefetch" href="/assets/js/20.4e91cd31.js"><link rel="prefetch" href="/assets/js/21.f095e6e1.js"><link rel="prefetch" href="/assets/js/22.72f4b8ab.js"><link rel="prefetch" href="/assets/js/23.e94eb9d2.js"><link rel="prefetch" href="/assets/js/24.0eae7d6f.js"><link rel="prefetch" href="/assets/js/25.36157609.js"><link rel="prefetch" href="/assets/js/26.dc5b6cba.js"><link rel="prefetch" href="/assets/js/27.c19b7b63.js"><link rel="prefetch" href="/assets/js/28.3aceae59.js"><link rel="prefetch" href="/assets/js/29.536091b3.js"><link rel="prefetch" href="/assets/js/3.d11119c4.js"><link rel="prefetch" href="/assets/js/30.821a4a30.js"><link rel="prefetch" href="/assets/js/31.5238784c.js"><link rel="prefetch" href="/assets/js/32.10bc7179.js"><link rel="prefetch" href="/assets/js/33.c1ed69c9.js"><link rel="prefetch" href="/assets/js/34.8d384231.js"><link rel="prefetch" href="/assets/js/35.d8890e52.js"><link rel="prefetch" href="/assets/js/36.eca37ad5.js"><link rel="prefetch" href="/assets/js/37.802549e3.js"><link rel="prefetch" href="/assets/js/38.53841770.js"><link rel="prefetch" href="/assets/js/39.7ae44409.js"><link rel="prefetch" href="/assets/js/4.493b9bca.js"><link rel="prefetch" href="/assets/js/40.ce56364a.js"><link rel="prefetch" href="/assets/js/41.85f0114b.js"><link rel="prefetch" href="/assets/js/42.714da6e2.js"><link rel="prefetch" href="/assets/js/43.fee4437c.js"><link rel="prefetch" href="/assets/js/44.b039b68b.js"><link rel="prefetch" href="/assets/js/45.96a55605.js"><link rel="prefetch" href="/assets/js/46.956ffb03.js"><link rel="prefetch" href="/assets/js/47.147d9218.js"><link rel="prefetch" href="/assets/js/48.ff787b40.js"><link rel="prefetch" href="/assets/js/49.871eee87.js"><link rel="prefetch" href="/assets/js/5.e0ba07d7.js"><link rel="prefetch" href="/assets/js/50.99b7c29e.js"><link rel="prefetch" href="/assets/js/51.8ecbf4ba.js"><link rel="prefetch" href="/assets/js/52.53d91d7e.js"><link rel="prefetch" href="/assets/js/53.af8a0d2a.js"><link rel="prefetch" href="/assets/js/54.a2f848b5.js"><link rel="prefetch" href="/assets/js/55.267e9947.js"><link rel="prefetch" href="/assets/js/56.0b201c40.js"><link rel="prefetch" href="/assets/js/57.cbdfd6f7.js"><link rel="prefetch" href="/assets/js/58.636c0c3f.js"><link rel="prefetch" href="/assets/js/59.fc9216c4.js"><link rel="prefetch" href="/assets/js/6.b98373f2.js"><link rel="prefetch" href="/assets/js/60.34f16fc4.js"><link rel="prefetch" href="/assets/js/61.4d130bd8.js"><link rel="prefetch" href="/assets/js/62.927caa10.js"><link rel="prefetch" href="/assets/js/63.a451fee0.js"><link rel="prefetch" href="/assets/js/64.32a5d47b.js"><link rel="prefetch" href="/assets/js/65.bc099429.js"><link rel="prefetch" href="/assets/js/66.3953050d.js"><link rel="prefetch" href="/assets/js/67.e934823b.js"><link rel="prefetch" href="/assets/js/68.4bcb52b0.js"><link rel="prefetch" href="/assets/js/69.bede18c8.js"><link rel="prefetch" href="/assets/js/7.8de8df2d.js"><link rel="prefetch" href="/assets/js/70.fce1daac.js"><link rel="prefetch" href="/assets/js/71.ea0a8c5d.js"><link rel="prefetch" href="/assets/js/72.15382c9e.js"><link rel="prefetch" href="/assets/js/73.848364d3.js"><link rel="prefetch" href="/assets/js/74.5fd08a50.js"><link rel="prefetch" href="/assets/js/75.c937c70d.js"><link rel="prefetch" href="/assets/js/76.a0dacd5a.js"><link rel="prefetch" href="/assets/js/77.4019cc23.js"><link rel="prefetch" href="/assets/js/78.9676a9e1.js"><link rel="prefetch" href="/assets/js/79.e46e10d5.js"><link rel="prefetch" href="/assets/js/8.2098eb96.js"><link rel="prefetch" href="/assets/js/80.987e83cb.js"><link rel="prefetch" href="/assets/js/81.eb98ff36.js"><link rel="prefetch" href="/assets/js/82.623561a7.js"><link rel="prefetch" href="/assets/js/83.e256d909.js"><link rel="prefetch" href="/assets/js/84.7d06a550.js"><link rel="prefetch" href="/assets/js/85.b8d9879e.js"><link rel="prefetch" href="/assets/js/86.31c4581b.js"><link rel="prefetch" href="/assets/js/87.e06ee05e.js"><link rel="prefetch" href="/assets/js/88.81ef718d.js"><link rel="prefetch" href="/assets/js/89.ba237d2f.js"><link rel="prefetch" href="/assets/js/9.36092fd0.js"><link rel="prefetch" href="/assets/js/90.ad2c9d92.js"><link rel="prefetch" href="/assets/js/91.a661f52d.js"><link rel="prefetch" href="/assets/js/92.1c28035b.js"><link rel="prefetch" href="/assets/js/93.c8b8e3d6.js"><link rel="prefetch" href="/assets/js/94.b6bc4a44.js"><link rel="prefetch" href="/assets/js/95.92cea882.js"><link rel="prefetch" href="/assets/js/96.5373491b.js"><link rel="prefetch" href="/assets/js/97.bb39efc8.js"><link rel="prefetch" href="/assets/js/98.af7a030f.js"><link rel="prefetch" href="/assets/js/99.07dc87d8.js">
    <link rel="stylesheet" href="/assets/css/0.styles.d9c8cf8c.css">
  </head>
  <body class="theme-mode-light">
    <div id="app" data-server-rendered="true"><div class="theme-container sidebar-open have-rightmenu"><header class="navbar blur"><div title="目录" class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><img src="https://lingxin-tanhua.oss-cn-shanghai.aliyuncs.com/QQ%E6%88%AA%E5%9B%BE20220503092755.png" alt="凌歆的博客" class="logo"> <span class="site-name can-hide">凌歆的博客</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端" class="dropdown-title"><a href="/web/" class="link-title">前端</a> <span class="title" style="display:none;">前端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>学习笔记</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/note/html/" class="nav-link">HTML笔记</a></li><li class="dropdown-subitem"><a href="/note/js-low/" class="nav-link">JavaScript基础笔记</a></li><li class="dropdown-subitem"><a href="/note/js-high/" class="nav-link">JavaScript高阶笔记</a></li><li class="dropdown-subitem"><a href="/note/js-dom-bom/" class="nav-link">JavaScript DOM和BOM笔记</a></li><li class="dropdown-subitem"><a href="/note/jquery/" class="nav-link">jQuery笔记</a></li><li class="dropdown-subitem"><a href="/note/ajax/" class="nav-link">Ajax笔记</a></li><li class="dropdown-subitem"><a href="/note/nodejs/" class="nav-link">NodeJs笔记</a></li><li class="dropdown-subitem"><a href="/note/reg/" class="nav-link">正则表达式笔记</a></li><li class="dropdown-subitem"><a href="/note/vue/" class="nav-link">Vue笔记</a></li><li class="dropdown-subitem"><a href="/note/react/" class="nav-link">react笔记</a></li><li class="dropdown-subitem"><a href="/note/wx/" class="nav-link">微信小程序笔记</a></li><li class="dropdown-subitem"><a href="/note/uniapp/" class="nav-link">uniapp笔记</a></li><li class="dropdown-subitem"><a href="/note/echarts/" class="nav-link">echarts笔记</a></li><li class="dropdown-subitem"><a href="/note/git/" class="nav-link">Git笔记</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="后端" class="dropdown-title"><a href="/back/" class="link-title">后端</a> <span class="title" style="display:none;">后端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/java/" class="nav-link">JAVA</a></li><li class="dropdown-item"><!----> <a href="/note/javaweb/" class="nav-link">JavaWeb</a></li><li class="dropdown-item"><!----> <a href="/note/mysql/" class="nav-link">MySql</a></li><li class="dropdown-item"><!----> <a href="/note/ssm/" class="nav-link">ssm</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法" class="dropdown-title"><a href="/algor/" class="link-title">算法</a> <span class="title" style="display:none;">算法</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/sf/" class="nav-link">算法训练营</a></li><li class="dropdown-item"><!----> <a href="/note/js-sf/" class="nav-link">js数据结构与算法</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="面试" class="dropdown-title"><a href="/mianshi/" class="link-title">面试</a> <span class="title" style="display:none;">面试</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/lqb/" class="nav-link">蓝桥杯备战</a></li><li class="dropdown-item"><!----> <a href="/note/ms/" class="nav-link">前端面试</a></li><li class="dropdown-item"><!----> <a href="/note/hmms/" class="nav-link">黑马面试</a></li><li class="dropdown-item"><!----> <a href="/note/xzms/" class="nav-link">校招零距离面试</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="解决方案" class="dropdown-title"><a href="/resolve/" class="link-title">解决方案</a> <span class="title" style="display:none;">解决方案</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/qd-resolve/" class="nav-link">前端解决方案</a></li><li class="dropdown-item"><!----> <a href="/note/hd-resolve/" class="nav-link">后端解决方案</a></li></ul></div></div><div class="nav-item"><a href="/pages/beb6c0bd8a66cea6/" class="nav-link">收藏</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="索引" class="dropdown-title"><a href="/archives/" class="link-title">索引</a> <span class="title" style="display:none;">索引</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">分类</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">标签</a></li><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">归档</a></li></ul></div></div> <a href="https://github.com/linxin1123/vuepress-blog" target="_blank" rel="noopener noreferrer" class="repo-link">
    GitHub
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar-hover-trigger"></div> <aside class="sidebar" style="display:none;"><div class="blogger"><img src="https://lingxin-tanhua.oss-cn-shanghai.aliyuncs.com/QQ%E6%88%AA%E5%9B%BE20220503092755.png"> <div class="blogger-info"><h3>lingxin</h3> <span>凌歆</span></div></div> <nav class="nav-links"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端" class="dropdown-title"><a href="/web/" class="link-title">前端</a> <span class="title" style="display:none;">前端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>学习笔记</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/note/html/" class="nav-link">HTML笔记</a></li><li class="dropdown-subitem"><a href="/note/js-low/" class="nav-link">JavaScript基础笔记</a></li><li class="dropdown-subitem"><a href="/note/js-high/" class="nav-link">JavaScript高阶笔记</a></li><li class="dropdown-subitem"><a href="/note/js-dom-bom/" class="nav-link">JavaScript DOM和BOM笔记</a></li><li class="dropdown-subitem"><a href="/note/jquery/" class="nav-link">jQuery笔记</a></li><li class="dropdown-subitem"><a href="/note/ajax/" class="nav-link">Ajax笔记</a></li><li class="dropdown-subitem"><a href="/note/nodejs/" class="nav-link">NodeJs笔记</a></li><li class="dropdown-subitem"><a href="/note/reg/" class="nav-link">正则表达式笔记</a></li><li class="dropdown-subitem"><a href="/note/vue/" class="nav-link">Vue笔记</a></li><li class="dropdown-subitem"><a href="/note/react/" class="nav-link">react笔记</a></li><li class="dropdown-subitem"><a href="/note/wx/" class="nav-link">微信小程序笔记</a></li><li class="dropdown-subitem"><a href="/note/uniapp/" class="nav-link">uniapp笔记</a></li><li class="dropdown-subitem"><a href="/note/echarts/" class="nav-link">echarts笔记</a></li><li class="dropdown-subitem"><a href="/note/git/" class="nav-link">Git笔记</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="后端" class="dropdown-title"><a href="/back/" class="link-title">后端</a> <span class="title" style="display:none;">后端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/java/" class="nav-link">JAVA</a></li><li class="dropdown-item"><!----> <a href="/note/javaweb/" class="nav-link">JavaWeb</a></li><li class="dropdown-item"><!----> <a href="/note/mysql/" class="nav-link">MySql</a></li><li class="dropdown-item"><!----> <a href="/note/ssm/" class="nav-link">ssm</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法" class="dropdown-title"><a href="/algor/" class="link-title">算法</a> <span class="title" style="display:none;">算法</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/sf/" class="nav-link">算法训练营</a></li><li class="dropdown-item"><!----> <a href="/note/js-sf/" class="nav-link">js数据结构与算法</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="面试" class="dropdown-title"><a href="/mianshi/" class="link-title">面试</a> <span class="title" style="display:none;">面试</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/lqb/" class="nav-link">蓝桥杯备战</a></li><li class="dropdown-item"><!----> <a href="/note/ms/" class="nav-link">前端面试</a></li><li class="dropdown-item"><!----> <a href="/note/hmms/" class="nav-link">黑马面试</a></li><li class="dropdown-item"><!----> <a href="/note/xzms/" class="nav-link">校招零距离面试</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="解决方案" class="dropdown-title"><a href="/resolve/" class="link-title">解决方案</a> <span class="title" style="display:none;">解决方案</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/qd-resolve/" class="nav-link">前端解决方案</a></li><li class="dropdown-item"><!----> <a href="/note/hd-resolve/" class="nav-link">后端解决方案</a></li></ul></div></div><div class="nav-item"><a href="/pages/beb6c0bd8a66cea6/" class="nav-link">收藏</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="索引" class="dropdown-title"><a href="/archives/" class="link-title">索引</a> <span class="title" style="display:none;">索引</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">分类</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">标签</a></li><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">归档</a></li></ul></div></div> <a href="https://github.com/linxin1123/vuepress-blog" target="_blank" rel="noopener noreferrer" class="repo-link">
    GitHub
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>学习笔记</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>算法训练营</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/pages/8ebdeb/" class="sidebar-link">数组-链表-栈-队列-cnblog</a></li><li><a href="/pages/8585b9/" class="sidebar-link">数组-链表-栈-队列（下）-cnblog</a></li><li><a href="/pages/1848ee/" class="sidebar-link">哈希表-集合-映射-cnblog</a></li><li><a href="/pages/32c8c0/" class="sidebar-link">前缀和-差分-双指针（上）-cnblog</a></li><li><a href="/pages/9b8692/" class="sidebar-link">前缀和-差分-双指针（下）-cnblog</a></li><li><a href="/pages/7f3ede/" class="sidebar-link">算法训练营-排序-cnblog</a></li><li><a href="/pages/cbca68/" class="sidebar-link">二分</a></li><li><a href="/pages/1a456e/" class="sidebar-link">三分-二分答案</a></li><li><a href="/pages/3fd3d8/" class="sidebar-link">树与图-cnblog</a></li><li><a href="/pages/7c3255/" class="sidebar-link">二叉搜索树</a></li><li><a href="/pages/cf81aa/" class="sidebar-link">二叉堆</a></li><li><a href="/pages/1cde21/" class="sidebar-link">递归-分治</a></li><li><a href="/pages/0e21af/" aria-current="page" class="active sidebar-link">深度-广度搜索-状态空间-cnblog</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/pages/6789f3/" class="sidebar-link">动态规划(一)</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>js数据结构与算法</span> <span class="arrow right"></span></p> <!----></section></li></ul> </aside> <div><main class="page"><div class="theme-vdoing-wrapper "><div class="articleInfo-wrap" data-v-06225672><div class="articleInfo" data-v-06225672><ul class="breadcrumbs" data-v-06225672><li data-v-06225672><a href="/" title="首页" class="iconfont icon-home router-link-active" data-v-06225672></a></li> <li data-v-06225672><a href="/algor/#算法" data-v-06225672>算法</a></li><li data-v-06225672><a href="/algor/#算法训练营" data-v-06225672>算法训练营</a></li></ul> <div class="info" data-v-06225672><div title="作者" class="author iconfont icon-touxiang" data-v-06225672><a href="https://github.com/linxin1123" target="_blank" title="作者" class="beLink" data-v-06225672>lingxin</a></div> <div title="创建时间" class="date iconfont icon-riqi" data-v-06225672><a href="javascript:;" data-v-06225672>2023-02-17</a></div> <!----></div></div></div> <!----> <div class="content-wrapper"><div class="right-menu-wrapper"><div class="right-menu-margin"><div class="right-menu-title">目录</div> <div class="right-menu-content"></div></div></div> <h1><img src="">深度-广度搜索-状态空间-cnblog<!----></h1>  <div class="theme-vdoing-content content__default"><p><img src="https://img2023.cnblogs.com/blog/3089561/202302/3089561-20230202230905636-1484514863.png" alt=""></p> <p><img src="https://img2023.cnblogs.com/blog/3089561/202302/3089561-20230202230905130-1892559224.png" alt="QQ截图20221020080038"></p> <ul><li><p>求子集</p></li> <li><p>上图把问题抽象成为图的遍历</p></li></ul> <h4 id="_17-电话号码的字母组合"><a href="#_17-电话号码的字母组合" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/" target="_blank" rel="noopener noreferrer">17. 电话号码的字母组合<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给定一个仅包含数字 <code>2-9</code> 的字符串，返回所有它能表示的字母组合。答案可以按 <strong>任意顺序</strong> 返回。</p> <p>给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。</p> <p><img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/11/09/200px-telephone-keypad2svg.png" alt="img"></p> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：digits = &quot;23&quot;
输出：[&quot;ad&quot;,&quot;ae&quot;,&quot;af&quot;,&quot;bd&quot;,&quot;be&quot;,&quot;bf&quot;,&quot;cd&quot;,&quot;ce&quot;,&quot;cf&quot;]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：digits = &quot;&quot;
输出：[]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 3：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：digits = &quot;2&quot;
输出：[&quot;a&quot;,&quot;b&quot;,&quot;c&quot;]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>0 &lt;= digits.length &lt;= 4</code></li> <li><code>digits[i]</code> 是范围 <code>['2', '9']</code> 的一个数字。</li></ul> <h5 id="解题思路"><a href="#解题思路" class="header-anchor">#</a> 解题思路</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token number">1.</span> 问题抽象为状态空间
<span class="token number">2.</span> 遍历所有可能的状态空间
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><h5 id="完整代码"><a href="#完整代码" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {string} digits
 * @return {string[]}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">letterCombinations</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">digits</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 我们使用搜索算法</span>

    <span class="token comment">// 把问题抽象成状态空间</span>

    <span class="token comment">// 变化的状态  index  s(结果字符串)</span>

    <span class="token comment">// 维护数字到字母字符串的映射</span>

    <span class="token keyword">let</span> edges<span class="token operator">=</span><span class="token punctuation">{</span>

        <span class="token string-property property">'2'</span><span class="token operator">:</span><span class="token punctuation">[</span><span class="token string">'a'</span><span class="token punctuation">,</span><span class="token string">'b'</span><span class="token punctuation">,</span><span class="token string">'c'</span><span class="token punctuation">]</span><span class="token punctuation">,</span>
        <span class="token string-property property">'3'</span><span class="token operator">:</span><span class="token punctuation">[</span><span class="token string">'d'</span><span class="token punctuation">,</span><span class="token string">'e'</span><span class="token punctuation">,</span><span class="token string">'f'</span><span class="token punctuation">]</span><span class="token punctuation">,</span>
        <span class="token string-property property">'4'</span><span class="token operator">:</span><span class="token punctuation">[</span><span class="token string">'g'</span><span class="token punctuation">,</span><span class="token string">'h'</span><span class="token punctuation">,</span><span class="token string">'i'</span><span class="token punctuation">]</span><span class="token punctuation">,</span>
        <span class="token string-property property">'5'</span><span class="token operator">:</span><span class="token punctuation">[</span><span class="token string">'j'</span><span class="token punctuation">,</span><span class="token string">'k'</span><span class="token punctuation">,</span><span class="token string">'l'</span><span class="token punctuation">]</span><span class="token punctuation">,</span>
        <span class="token string-property property">'6'</span><span class="token operator">:</span><span class="token punctuation">[</span><span class="token string">'m'</span><span class="token punctuation">,</span><span class="token string">'n'</span><span class="token punctuation">,</span><span class="token string">'o'</span><span class="token punctuation">]</span><span class="token punctuation">,</span>
        <span class="token string-property property">'7'</span><span class="token operator">:</span><span class="token punctuation">[</span><span class="token string">'p'</span><span class="token punctuation">,</span><span class="token string">'q'</span><span class="token punctuation">,</span><span class="token string">'r'</span><span class="token punctuation">,</span><span class="token string">'s'</span><span class="token punctuation">]</span><span class="token punctuation">,</span>
        <span class="token string-property property">'8'</span><span class="token operator">:</span><span class="token punctuation">[</span><span class="token string">'t'</span><span class="token punctuation">,</span><span class="token string">'u'</span><span class="token punctuation">,</span><span class="token string">'v'</span><span class="token punctuation">]</span><span class="token punctuation">,</span>
        <span class="token string-property property">'9'</span><span class="token operator">:</span><span class="token punctuation">[</span><span class="token string">'w'</span><span class="token punctuation">,</span><span class="token string">'x'</span><span class="token punctuation">,</span><span class="token string">'y'</span><span class="token punctuation">,</span><span class="token string">'z'</span><span class="token punctuation">]</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">let</span> s<span class="token operator">=</span><span class="token string">''</span>
    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    
    

    <span class="token comment">// 遍历状态空间</span>
    <span class="token keyword">const</span> <span class="token function-variable function">dfs</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">s<span class="token punctuation">,</span>index</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>

        <span class="token comment">// 到达深搜终点，返回</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>s<span class="token punctuation">.</span>length<span class="token operator">===</span>digits<span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>s<span class="token punctuation">.</span>length<span class="token operator">===</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">return</span> 
            res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span>
            <span class="token keyword">return</span> 
        <span class="token punctuation">}</span>
        
        <span class="token comment">// 出边数组，即下一步可能的出边</span>
        <span class="token comment">// console.log(edges[digits[0]])</span>
        <span class="token keyword">let</span> arr<span class="token operator">=</span>edges<span class="token punctuation">[</span>digits<span class="token punctuation">[</span>index<span class="token punctuation">]</span><span class="token punctuation">]</span>

        <span class="token comment">// 走向不同的状态空间</span>

        arr<span class="token punctuation">.</span><span class="token function">forEach</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token parameter">item</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
            <span class="token function">dfs</span><span class="token punctuation">(</span>s<span class="token operator">+</span>item<span class="token punctuation">,</span>index<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token punctuation">}</span><span class="token punctuation">)</span>

    <span class="token punctuation">}</span>

    <span class="token function">dfs</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token keyword">return</span> res

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br></div></div><h4 id="_51-n-皇后"><a href="#_51-n-皇后" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/n-queens/" target="_blank" rel="noopener noreferrer">51. N 皇后<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。</p> <p><strong>n 皇后问题</strong> 研究的是如何将 <code>n</code> 个皇后放置在 <code>n×n</code> 的棋盘上，并且使皇后彼此之间不能相互攻击。</p> <p>给你一个整数 <code>n</code> ，返回所有不同的 <strong>n 皇后问题</strong> 的解决方案。</p> <p>每一种解法包含一个不同的 <strong>n 皇后问题</strong> 的棋子放置方案，该方案中 <code>'Q'</code> 和 <code>'.'</code> 分别代表了皇后和空位。</p> <p><strong>示例 1：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/11/13/queens.jpg" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：n = 4
输出：[[&quot;.Q..&quot;,&quot;...Q&quot;,&quot;Q...&quot;,&quot;..Q.&quot;],[&quot;..Q.&quot;,&quot;Q...&quot;,&quot;...Q&quot;,&quot;.Q..&quot;]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：n = 1
输出：[[&quot;Q&quot;]]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li><p><code>1 &lt;= n &lt;= 9</code></p></li> <li><p>判断对角线的方法</p></li></ul> <p><img src="https://img2023.cnblogs.com/blog/3089561/202302/3089561-20230202230859187-234855936.jpg" alt=""></p> <h5 id="解题思路-2"><a href="#解题思路-2" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 全排列的状态空间
<span class="token number">2</span>. 在全排列的基础上排除有对角线的
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><h5 id="完整代码-2"><a href="#完整代码-2" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {number} n
 * @return {string[][]}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">solveNQueens</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">n</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 先计算出全排列</span>

    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token comment">// 定义对角线是否使用对象</span>
    <span class="token keyword">let</span> useIplusJ<span class="token operator">=</span><span class="token punctuation">{</span><span class="token punctuation">}</span>
    <span class="token keyword">let</span> useIminsJ<span class="token operator">=</span><span class="token punctuation">{</span><span class="token punctuation">}</span>


    
    <span class="token keyword">const</span> <span class="token function-variable function">dfs</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">arr</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>

        <span class="token keyword">let</span> depth<span class="token operator">=</span>arr<span class="token punctuation">.</span>length

        <span class="token keyword">if</span><span class="token punctuation">(</span>arr<span class="token punctuation">.</span>length<span class="token operator">===</span>n<span class="token punctuation">)</span><span class="token punctuation">{</span>
            res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>Array<span class="token punctuation">.</span><span class="token function">from</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>arr<span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token operator">&amp;&amp;</span><span class="token operator">!</span>useIplusJ<span class="token punctuation">[</span>depth<span class="token operator">+</span>i<span class="token punctuation">]</span><span class="token operator">&amp;&amp;</span><span class="token operator">!</span>useIminsJ<span class="token punctuation">[</span>depth<span class="token operator">-</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>

                <span class="token comment">// 我们在加上对角线的限制</span>
                useIplusJ<span class="token punctuation">[</span>depth<span class="token operator">+</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">true</span>
                useIminsJ<span class="token punctuation">[</span>depth<span class="token operator">-</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">true</span>
                <span class="token function">dfs</span><span class="token punctuation">(</span>arr<span class="token punctuation">.</span><span class="token function">concat</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">)</span>

                useIplusJ<span class="token punctuation">[</span>depth<span class="token operator">+</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">false</span>
                useIminsJ<span class="token punctuation">[</span>depth<span class="token operator">-</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">false</span>
            <span class="token punctuation">}</span>   
        <span class="token punctuation">}</span>
        
    <span class="token punctuation">}</span>

    <span class="token function">dfs</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span>

    console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span>

    <span class="token keyword">const</span> newRes<span class="token operator">=</span>res<span class="token punctuation">.</span><span class="token function">map</span><span class="token punctuation">(</span><span class="token parameter">item</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>

        <span class="token keyword">return</span> item<span class="token punctuation">.</span><span class="token function">map</span><span class="token punctuation">(</span><span class="token parameter">ele</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
            <span class="token keyword">let</span> s<span class="token operator">=</span><span class="token string">''</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">===</span>ele<span class="token punctuation">)</span><span class="token punctuation">{</span>
                    s<span class="token operator">+=</span><span class="token string">'Q'</span>
                <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span>
                    s<span class="token operator">+=</span><span class="token string">'.'</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>

            <span class="token keyword">return</span> s
        <span class="token punctuation">}</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span><span class="token punctuation">)</span>

    <span class="token keyword">return</span> newRes

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br></div></div><h4 id="_200-岛屿数量-地图dfs模板题"><a href="#_200-岛屿数量-地图dfs模板题" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/number-of-islands/" target="_blank" rel="noopener noreferrer">200. 岛屿数量(地图dfs模板题)<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给你一个由 <code>'1'</code>（陆地）和 <code>'0'</code>（水）组成的的二维网格，请你计算网格中岛屿的数量。</p> <p>岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。</p> <p>此外，你可以假设该网格的四条边均被水包围。</p> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;]
]
输出：1
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;]
]
输出：3
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>m == grid.length</code></li> <li><code>n == grid[i].length</code></li> <li><code>1 &lt;= m, n &lt;= 300</code></li> <li><code>grid[i][j]</code> 的值为 <code>'0'</code> 或 <code>'1'</code></li></ul> <h5 id="解题思路-3"><a href="#解题思路-3" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 需要理解题意
<span class="token number">2</span>. 找岛屿个数，其实是找所有相互连接（相邻）的1的集群
<span class="token number">3</span>. 集群的个数即为岛屿的个数
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><h5 id="地图dfs"><a href="#地图dfs" class="header-anchor">#</a> 地图dfs</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code>/**
 * @param <span class="token punctuation">{</span>character<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">}</span> grid
 * @return <span class="token punctuation">{</span>number<span class="token punctuation">}</span>
 */
var numIslands <span class="token operator">=</span> function<span class="token punctuation">(</span>grid<span class="token punctuation">)</span> <span class="token punctuation">{</span>

    // 即寻找1的所有连通图

    <span class="token builtin class-name">let</span> <span class="token assign-left variable">res</span><span class="token operator">=</span><span class="token number">0</span>
    // 行
    <span class="token builtin class-name">let</span> <span class="token assign-left variable">m</span><span class="token operator">=</span>grid.length
    // 列
    <span class="token builtin class-name">let</span> <span class="token assign-left variable">n</span><span class="token operator">=</span>grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>.length
    // 访问数组
    <span class="token builtin class-name">let</span> <span class="token assign-left variable">visited</span><span class="token operator">=</span>new Array<span class="token punctuation">(</span>m<span class="token punctuation">)</span>
    for<span class="token punctuation">(</span>let <span class="token assign-left variable">i</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i++<span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token builtin class-name">let</span> <span class="token assign-left variable">arr</span><span class="token operator">=</span>new Array<span class="token punctuation">(</span>n<span class="token punctuation">)</span>.fill<span class="token punctuation">(</span>false<span class="token punctuation">)</span>
        visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>arr
    <span class="token punctuation">}</span>

    // 定义一个方向数组

    <span class="token builtin class-name">let</span> <span class="token assign-left variable">dx</span><span class="token operator">=</span><span class="token punctuation">[</span>-1,0,1,0<span class="token punctuation">]</span>
    <span class="token builtin class-name">let</span> <span class="token assign-left variable">dy</span><span class="token operator">=</span><span class="token punctuation">[</span><span class="token number">0,1</span>,0,-1<span class="token punctuation">]</span>
    const <span class="token assign-left variable">dfs</span><span class="token operator">=</span><span class="token punctuation">(</span>x,y<span class="token punctuation">)</span><span class="token operator">=</span><span class="token operator">&gt;</span><span class="token punctuation">{</span>
        visited<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token operator">=</span>true

        // 寻找当前节点的所有出边，即相邻的方向

        for<span class="token punctuation">(</span>let <span class="token assign-left variable">i</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">4</span><span class="token punctuation">;</span>i++<span class="token punctuation">)</span><span class="token punctuation">{</span>
            // <span class="token number">4</span>个方向
            <span class="token builtin class-name">let</span> <span class="token assign-left variable">nx</span><span class="token operator">=</span>x+dx<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            <span class="token builtin class-name">let</span> <span class="token assign-left variable">ny</span><span class="token operator">=</span>y+dy<span class="token punctuation">[</span>i<span class="token punctuation">]</span>

            if<span class="token punctuation">(</span>nx<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>ny<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>nx<span class="token operator">&gt;=</span>m<span class="token operator">||</span>ny<span class="token operator">&gt;=</span>n<span class="token punctuation">)</span> <span class="token builtin class-name">continue</span>

            // 合法
            if<span class="token punctuation">(</span>grid<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token operator">==</span><span class="token operator">=</span><span class="token string">'1'</span><span class="token operator">&amp;&amp;</span><span class="token operator">!</span>visited<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                dfs<span class="token punctuation">(</span>nx,ny<span class="token punctuation">)</span>
            <span class="token punctuation">}</span>

        <span class="token punctuation">}</span>

    <span class="token punctuation">}</span>

    // 寻找连通图的个数
    for<span class="token punctuation">(</span>let <span class="token assign-left variable">i</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i++<span class="token punctuation">)</span><span class="token punctuation">{</span>
        for<span class="token punctuation">(</span>let <span class="token assign-left variable">j</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>j++<span class="token punctuation">)</span><span class="token punctuation">{</span>
            
            if<span class="token punctuation">(</span>grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">==</span><span class="token operator">=</span><span class="token string">'1'</span><span class="token operator">&amp;&amp;</span><span class="token operator">!</span>visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                dfs<span class="token punctuation">(</span>i,j<span class="token punctuation">)</span>
                res++
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>


    <span class="token builtin class-name">return</span> res

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br></div></div><h5 id="地图bfs"><a href="#地图bfs" class="header-anchor">#</a> 地图bfs</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {character[][]} grid
 * @return {number}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">numIslands</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">grid</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 广度优先搜索</span>

    <span class="token comment">// 找有几个连通图</span>

    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token number">0</span>

    <span class="token keyword">let</span> m<span class="token operator">=</span>grid<span class="token punctuation">.</span>length
    <span class="token keyword">let</span> n<span class="token operator">=</span>grid<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>length

    <span class="token comment">// 方向数组</span>
    <span class="token keyword">let</span> dx<span class="token operator">=</span><span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">]</span>
    <span class="token keyword">let</span> dy<span class="token operator">=</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>

    <span class="token comment">// 定义一个visited数组，记录是否被访问</span>
    <span class="token keyword">let</span> visited<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>m<span class="token punctuation">)</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">let</span> arr<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token boolean">false</span><span class="token punctuation">)</span>
        visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>arr
    <span class="token punctuation">}</span>

    <span class="token comment">// console.log(visited)</span>

    <span class="token keyword">const</span> <span class="token function-variable function">bfs</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">x<span class="token punctuation">,</span>y</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        <span class="token comment">// 广度优先搜索，维护一个队列</span>

        <span class="token keyword">let</span> queue<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

        queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token punctuation">[</span>x<span class="token punctuation">,</span>y<span class="token punctuation">]</span><span class="token punctuation">)</span>
        visited<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">true</span>

        <span class="token keyword">while</span><span class="token punctuation">(</span>queue<span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>

            <span class="token keyword">let</span> first<span class="token operator">=</span>queue<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
            <span class="token keyword">let</span> second<span class="token operator">=</span>queue<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span>

            queue<span class="token punctuation">.</span><span class="token function">shift</span><span class="token punctuation">(</span><span class="token punctuation">)</span>

            <span class="token comment">// 遍历所有的出边</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">4</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token keyword">let</span> nx<span class="token operator">=</span>first<span class="token operator">+</span>dx<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
                <span class="token keyword">let</span> ny<span class="token operator">=</span>second<span class="token operator">+</span>dy<span class="token punctuation">[</span>i<span class="token punctuation">]</span>

                <span class="token keyword">if</span><span class="token punctuation">(</span>nx<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>ny<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>nx<span class="token operator">&gt;=</span>m<span class="token operator">||</span>ny<span class="token operator">&gt;=</span>n<span class="token punctuation">)</span> <span class="token keyword">continue</span>

                <span class="token keyword">if</span><span class="token punctuation">(</span>grid<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token operator">===</span><span class="token string">'1'</span><span class="token operator">&amp;&amp;</span><span class="token operator">!</span>visited<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                    queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token punctuation">[</span>nx<span class="token punctuation">,</span>ny<span class="token punctuation">]</span><span class="token punctuation">)</span>
                    console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span><span class="token string">'nx'</span><span class="token punctuation">,</span>nx<span class="token punctuation">,</span><span class="token string">'ny'</span><span class="token punctuation">,</span>ny<span class="token punctuation">)</span>
                    visited<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">true</span>
                <span class="token punctuation">}</span>

                
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 开始遍历没有访问过的1</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>

            <span class="token keyword">if</span><span class="token punctuation">(</span>grid<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">===</span><span class="token string">'1'</span><span class="token operator">&amp;&amp;</span><span class="token operator">!</span>visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token comment">// console.log(i,j)</span>
                <span class="token function">bfs</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span>j<span class="token punctuation">)</span>
                <span class="token comment">// console.log(visited)</span>
                res<span class="token operator">++</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> res

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br></div></div><h4 id="_130-被围绕的区域"><a href="#_130-被围绕的区域" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/surrounded-regions/description/" target="_blank" rel="noopener noreferrer">130. 被围绕的区域<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给你一个 <code>m x n</code> 的矩阵 <code>board</code> ，由若干字符 <code>'X'</code> 和 <code>'O'</code> ，找到所有被 <code>'X'</code> 围绕的区域，并将这些区域里所有的 <code>'O'</code> 用 <code>'X'</code> 填充。</p> <p><strong>示例 1：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/02/19/xogrid.jpg" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：board = [[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;O&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;O&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;X&quot;,&quot;X&quot;]]
输出：[[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;X&quot;,&quot;X&quot;]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：board = [[&quot;X&quot;]]
输出：[[&quot;X&quot;]]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>m == board.length</code></li> <li><code>n == board[i].length</code></li> <li><code>1 &lt;= m, n &lt;= 200</code></li> <li><code>board[i][j]</code> 为 <code>'X'</code> 或 <code>'O'</code></li></ul> <h5 id="解题思路-4"><a href="#解题思路-4" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 还是找连通图
<span class="token number">2</span>. 不过加上了限制条件，不能选取连接在边缘的连通图
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><h5 id="完整代码-3"><a href="#完整代码-3" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">solve</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">board</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token keyword">let</span> m<span class="token operator">=</span>board<span class="token punctuation">.</span>length
    <span class="token keyword">let</span> n<span class="token operator">=</span>board<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>length

    <span class="token keyword">let</span> visited<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>m<span class="token punctuation">)</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">let</span> arr<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token boolean">false</span><span class="token punctuation">)</span>

        visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>arr
    <span class="token punctuation">}</span>

    <span class="token comment">// 存放需要修改的下标数组</span>
    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token comment">// 连通图访问，如果判断为封闭，push到res</span>
    <span class="token keyword">let</span> temp<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token comment">// 判断区域是否被环绕</span>
    <span class="token keyword">var</span> has<span class="token operator">=</span><span class="token boolean">false</span>

    <span class="token keyword">let</span> dx<span class="token operator">=</span><span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">]</span>
    <span class="token keyword">let</span> dy<span class="token operator">=</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>

    <span class="token keyword">const</span> <span class="token function-variable function">dfs</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">x<span class="token punctuation">,</span>y</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        temp<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token punctuation">[</span>x<span class="token punctuation">,</span>y<span class="token punctuation">]</span><span class="token punctuation">)</span>
        visited<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token operator">=</span><span class="token boolean">true</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">4</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            nx<span class="token operator">=</span>x<span class="token operator">+</span>dx<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            ny<span class="token operator">=</span>y<span class="token operator">+</span>dy<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            
            <span class="token comment">// 合法性判断</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>nx<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>ny<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>nx<span class="token operator">&gt;=</span>m<span class="token operator">||</span>ny<span class="token operator">&gt;=</span>n<span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token keyword">continue</span>
            <span class="token punctuation">}</span>

            <span class="token comment">// O走到了边缘，不是被环绕</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token punctuation">(</span>nx<span class="token operator">===</span><span class="token number">0</span><span class="token operator">||</span>ny<span class="token operator">===</span><span class="token number">0</span><span class="token operator">||</span>nx<span class="token operator">===</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token operator">||</span>ny<span class="token operator">===</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token comment">// console.log('nx',nx,'ny',ny)</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>visited<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token operator">&amp;&amp;</span>board<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token operator">===</span><span class="token string">'O'</span><span class="token punctuation">)</span>
                has<span class="token operator">=</span><span class="token boolean">true</span>
                <span class="token comment">// break</span>
            <span class="token punctuation">}</span>


            <span class="token comment">// 不是边缘，继续走</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>board<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token operator">===</span><span class="token string">'O'</span><span class="token operator">&amp;&amp;</span><span class="token operator">!</span>visited<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                
                <span class="token function">dfs</span><span class="token punctuation">(</span>nx<span class="token punctuation">,</span>ny<span class="token punctuation">)</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token comment">// visited[x][y]=false</span>
    <span class="token punctuation">}</span>

    

    <span class="token comment">// 我们从零开始遍历联通</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            
            <span class="token comment">// 边缘我们不考虑</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span><span class="token number">0</span><span class="token operator">||</span>j<span class="token operator">===</span><span class="token number">0</span><span class="token operator">||</span>i<span class="token operator">===</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token operator">||</span>j<span class="token operator">===</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">continue</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>board<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">===</span><span class="token string">'O'</span><span class="token operator">&amp;&amp;</span><span class="token operator">!</span>visited<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                
                has<span class="token operator">=</span><span class="token boolean">false</span>
                <span class="token comment">// 存放走过的O，可能是正确解</span>
                temp<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
                <span class="token function">dfs</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span>j<span class="token punctuation">)</span>
                
                <span class="token comment">// 确实被环绕</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>has<span class="token punctuation">)</span><span class="token punctuation">{</span>
                    res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>Array<span class="token punctuation">.</span><span class="token function">from</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">)</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span>
    <span class="token comment">// 将被环绕的点修改为X</span>
    res<span class="token punctuation">.</span><span class="token function">forEach</span><span class="token punctuation">(</span><span class="token parameter">item</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        item<span class="token punctuation">.</span><span class="token function">forEach</span><span class="token punctuation">(</span><span class="token parameter">item2</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
            board<span class="token punctuation">[</span>item2<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">[</span>item2<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token string">'X'</span>
        <span class="token punctuation">}</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span><span class="token punctuation">)</span>
    
    <span class="token comment">// return []</span>

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br><span class="line-number">84</span><br><span class="line-number">85</span><br><span class="line-number">86</span><br><span class="line-number">87</span><br><span class="line-number">88</span><br><span class="line-number">89</span><br><span class="line-number">90</span><br><span class="line-number">91</span><br><span class="line-number">92</span><br><span class="line-number">93</span><br><span class="line-number">94</span><br><span class="line-number">95</span><br></div></div><h4 id="_433-最小基因变化"><a href="#_433-最小基因变化" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/minimum-genetic-mutation/description/" target="_blank" rel="noopener noreferrer">433. 最小基因变化<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 <code>'A'</code>、<code>'C'</code>、<code>'G'</code> 和 <code>'T'</code> 之一。</p> <p>假设我们需要调查从基因序列 <code>start</code> 变为 <code>end</code> 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。</p> <ul><li>例如，<code>&quot;AACCGGTT&quot; --&gt; &quot;AACCGGTA&quot;</code> 就是一次基因变化。</li></ul> <p>另有一个基因库 <code>bank</code> 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 <code>bank</code> 中）</p> <p>给你两个基因序列 <code>start</code> 和 <code>end</code> ，以及一个基因库 <code>bank</code> ，请你找出并返回能够使 <code>start</code> 变化为 <code>end</code> 所需的最少变化次数。如果无法完成此基因变化，返回 <code>-1</code> 。</p> <p>注意：起始基因序列 <code>start</code> 默认是有效的，但是它并不一定会出现在基因库中。</p> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：start = &quot;AACCGGTT&quot;, end = &quot;AACCGGTA&quot;, bank = [&quot;AACCGGTA&quot;]
输出：1
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：start = &quot;AACCGGTT&quot;, end = &quot;AAACGGTA&quot;, bank = [&quot;AACCGGTA&quot;,&quot;AACCGCTA&quot;,&quot;AAACGGTA&quot;]
输出：2
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 3：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：start = &quot;AAAAACCC&quot;, end = &quot;AACCCCCC&quot;, bank = [&quot;AAAACCCC&quot;,&quot;AAACCCCC&quot;,&quot;AACCCCCC&quot;]
输出：3
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>start.length == 8</code></li> <li><code>end.length == 8</code></li> <li><code>0 &lt;= bank.length &lt;= 10</code></li> <li><code>bank[i].length == 8</code></li> <li><code>start</code>、<code>end</code> 和 <code>bank[i]</code> 仅由字符 <code>['A', 'C', 'G', 'T']</code> 组成</li></ul> <h5 id="解题思路-5"><a href="#解题思路-5" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 写出状态空间，根据状态空间搜索
<span class="token number">2</span>. 因为题目是看变化最小次数达到目的，适合实验bfs搜索
<span class="token number">3</span>. 搜索的层数即为变化的次数
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><h5 id="完整代码-4"><a href="#完整代码-4" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">minMutation</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">start<span class="token punctuation">,</span> end<span class="token punctuation">,</span> bank</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 解题思路</span>
    <span class="token comment">// 画出所有的状态空间</span>

    <span class="token comment">// 基因长度为8</span>
    <span class="token comment">// 总的基于序列个数  4^8</span>

    <span class="token comment">// 对于每个基因，变化1次，出边 3*8</span>

    <span class="token comment">// 则规模 4^8 *24</span>

    <span class="token comment">// 广度优先搜索</span>

    <span class="token comment">// 在第n层搜到，说明变化次数即为n次</span>

    
    <span class="token keyword">let</span> queue<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
    <span class="token comment">// 存储每个节点对应的深度</span>
    <span class="token keyword">let</span> depth<span class="token operator">=</span><span class="token punctuation">{</span><span class="token punctuation">}</span>

    <span class="token keyword">let</span> gens<span class="token operator">=</span><span class="token punctuation">[</span><span class="token string">'A'</span><span class="token punctuation">,</span><span class="token string">'C'</span><span class="token punctuation">,</span><span class="token string">'G'</span><span class="token punctuation">,</span><span class="token string">'T'</span><span class="token punctuation">]</span>

    <span class="token comment">// 广度，维护一个队列</span>
    queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>start<span class="token punctuation">)</span>
    depth<span class="token punctuation">[</span>start<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>queue<span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token keyword">let</span> str<span class="token operator">=</span>queue<span class="token punctuation">.</span><span class="token function">shift</span><span class="token punctuation">(</span><span class="token punctuation">)</span>

        <span class="token comment">// 开始变化，变化一次</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">8</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span><span class="token number">4</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                
                <span class="token keyword">if</span><span class="token punctuation">(</span>str<span class="token punctuation">.</span><span class="token function">charAt</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token operator">!==</span>gens<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>

                    <span class="token comment">// 变化成新的字符串</span>
                    <span class="token keyword">let</span> newStr<span class="token operator">=</span><span class="token string">''</span>
                    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> m<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>m<span class="token operator">&lt;</span><span class="token number">8</span><span class="token punctuation">;</span>m<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                        <span class="token keyword">if</span><span class="token punctuation">(</span>m<span class="token operator">===</span>i<span class="token punctuation">)</span><span class="token punctuation">{</span>
                            newStr<span class="token operator">+=</span>gens<span class="token punctuation">[</span>j<span class="token punctuation">]</span>
                        <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span>
                            newStr<span class="token operator">+=</span>str<span class="token punctuation">[</span>m<span class="token punctuation">]</span>
                        <span class="token punctuation">}</span>
                    <span class="token punctuation">}</span>

                    <span class="token comment">// 判断新的字符串是否合法</span>
                    <span class="token keyword">if</span><span class="token punctuation">(</span>bank<span class="token punctuation">.</span><span class="token function">includes</span><span class="token punctuation">(</span>newStr<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                        
                        <span class="token comment">// 产生的新基因没有访问过</span>
                        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>depth<span class="token punctuation">[</span>newStr<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                            <span class="token comment">// console.log(newStr)</span>
                            depth<span class="token punctuation">[</span>newStr<span class="token punctuation">]</span><span class="token operator">=</span>depth<span class="token punctuation">[</span>str<span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span>
                            queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>newStr<span class="token punctuation">)</span>
                            <span class="token keyword">if</span><span class="token punctuation">(</span>newStr<span class="token operator">===</span>end<span class="token punctuation">)</span><span class="token punctuation">{</span>
                                <span class="token keyword">return</span> depth<span class="token punctuation">[</span>newStr<span class="token punctuation">]</span>
                            <span class="token punctuation">}</span>
                        <span class="token punctuation">}</span>
                    <span class="token punctuation">}</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span>
    
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br></div></div><h4 id="_329-矩阵中的最长递增路径"><a href="#_329-矩阵中的最长递增路径" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/" target="_blank" rel="noopener noreferrer">329. 矩阵中的最长递增路径<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给定一个 <code>m x n</code> 整数矩阵 <code>matrix</code> ，找出其中 <strong>最长递增路径</strong> 的长度。</p> <p>对于每个单元格，你可以往上，下，左，右四个方向移动。 你 <strong>不能</strong> 在 <strong>对角线</strong> 方向上移动或移动到 <strong>边界外</strong>（即不允许环绕）。</p> <p><strong>示例 1：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/01/05/grid1.jpg" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 2：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/01/27/tmp-grid.jpg" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 3：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：matrix = [[1]]
输出：1
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>m == matrix.length</code></li> <li><code>n == matrix[i].length</code></li> <li><code>1 &lt;= m, n &lt;= 200</code></li> <li><code>0 &lt;= matrix[i][j] &lt;= 231 - 1</code></li></ul> <h5 id="解题思路-6"><a href="#解题思路-6" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. dfs 暴力，遍历每个节点能走的深度，取出最大值，超时

<span class="token number">2</span>. dfs+记忆数组
   遍历每个节点能走的深度，同时记录这个深度，这样其他
   节点获取深度时，可以根据已经记录的深度，减少计算量
   
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><h5 id="dfs-记忆化-完整代码"><a href="#dfs-记忆化-完整代码" class="header-anchor">#</a> dfs+记忆化 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {number[][]} matrix
 * @return {number}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">longestIncreasingPath</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">matrix</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>


    <span class="token comment">// 使用普通的dfs会超时</span>
    
    <span class="token comment">// dfs+记忆化</span>

    <span class="token comment">// 我们记忆每个格子往高处走，能走多远</span>

    <span class="token comment">// 其实不需要visited数组，为什么</span>
    <span class="token comment">// 因为只能往高处走，不会形成环</span>

    <span class="token keyword">let</span> m<span class="token operator">=</span>matrix<span class="token punctuation">.</span>length
    <span class="token keyword">let</span> n<span class="token operator">=</span>matrix<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>length
    <span class="token comment">// 使用dfs</span>
    <span class="token comment">// let visited=new Array(m)</span>

    <span class="token comment">// 记录每个格子能走多远</span>

    <span class="token keyword">let</span> howFar<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>m<span class="token punctuation">)</span>


    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token comment">// let arr=new Array(n).fill(false)</span>
        <span class="token keyword">let</span> arr1<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token comment">// visited[i]=arr</span>
        howFar<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>arr1
    <span class="token punctuation">}</span>

    <span class="token keyword">let</span> dx<span class="token operator">=</span><span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">]</span>
    <span class="token keyword">let</span> dy<span class="token operator">=</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>

    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token operator">-</span><span class="token number">1</span>

    

    <span class="token keyword">const</span> <span class="token function-variable function">dfs</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">x<span class="token punctuation">,</span>y</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        
        <span class="token keyword">if</span><span class="token punctuation">(</span>howFar<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token operator">!==</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token keyword">return</span> howFar<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span>

        <span class="token comment">// 开始遍历所有的出边</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">4</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">let</span> nx<span class="token operator">=</span>x<span class="token operator">+</span>dx<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            <span class="token keyword">let</span> ny<span class="token operator">=</span>y<span class="token operator">+</span>dy<span class="token punctuation">[</span>i<span class="token punctuation">]</span>

            <span class="token keyword">if</span><span class="token punctuation">(</span>nx<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>ny<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>nx<span class="token operator">&gt;=</span>m<span class="token operator">||</span>ny<span class="token operator">&gt;=</span>n<span class="token punctuation">)</span> <span class="token keyword">continue</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>matrix<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token operator">&gt;</span>matrix<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                howFar<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token operator">=</span>Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>howFar<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token function">dfs</span><span class="token punctuation">(</span>nx<span class="token punctuation">,</span>ny<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span>
            <span class="token punctuation">}</span>

        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> howFar<span class="token punctuation">[</span>x<span class="token punctuation">]</span><span class="token punctuation">[</span>y<span class="token punctuation">]</span>
        
    <span class="token punctuation">}</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            res<span class="token operator">=</span>Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>res<span class="token punctuation">,</span><span class="token function">dfs</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span>j<span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> res

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br></div></div><h5 id="bfs"><a href="#bfs" class="header-anchor">#</a> bfs</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {number[][]} matrix
 * @return {number}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">longestIncreasingPath</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">matrix</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// bfs进行拓扑排序</span>

  <span class="token comment">// 我们遍历节点从入度为0的开始</span>

  <span class="token comment">// 遍历它的出边数组时，把出边对应的入度-1</span>

  <span class="token keyword">let</span> m <span class="token operator">=</span> matrix<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
  <span class="token keyword">let</span> n <span class="token operator">=</span> matrix<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>length<span class="token punctuation">;</span>

  <span class="token keyword">let</span> dx <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
  <span class="token keyword">let</span> dy <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

  <span class="token comment">// 这里deg数组使用了二维数组，其实可以使用一维数组（降维，压缩）</span>
  <span class="token keyword">let</span> inDeg <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>m <span class="token operator">*</span> n<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

  <span class="token comment">// 出边数组，如果直接存储，数组为变成三维，比较难维护，我们降维</span>

  <span class="token keyword">let</span> edges <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

  <span class="token comment">// 距离数组，记录每个节点能走的最大值，默认是1</span>
  <span class="token keyword">let</span> dist <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Array</span><span class="token punctuation">(</span>m <span class="token operator">*</span> n<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">fill</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m <span class="token operator">*</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">let</span> arr <span class="token operator">=</span> Array<span class="token punctuation">.</span><span class="token function">from</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    edges<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 遍历所有节点，存储入度数组</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> k <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> k <span class="token operator">&lt;</span> <span class="token number">4</span><span class="token punctuation">;</span> k<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> nx <span class="token operator">=</span> i <span class="token operator">+</span> dx<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> ny <span class="token operator">=</span> j <span class="token operator">+</span> dy<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>nx <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> ny <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> nx <span class="token operator">&gt;=</span> m <span class="token operator">||</span> ny <span class="token operator">&gt;=</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span>
          <span class="token keyword">continue</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>matrix<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span> <span class="token operator">&lt;</span> matrix<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
          inDeg<span class="token punctuation">[</span>i <span class="token operator">*</span> n <span class="token operator">+</span> j<span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>matrix<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">&lt;</span> matrix<span class="token punctuation">[</span>nx<span class="token punctuation">]</span><span class="token punctuation">[</span>ny<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
          edges<span class="token punctuation">[</span>i <span class="token operator">*</span> n <span class="token operator">+</span> j<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>nx <span class="token operator">*</span> n <span class="token operator">+</span> ny<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
      <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>

  

<span class="token comment">//   console.log(inDeg);</span>
<span class="token comment">//   console.log(edges);</span>

  <span class="token keyword">const</span> <span class="token function-variable function">tpSort</span> <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
    <span class="token comment">// 开始拓扑排序</span>
    <span class="token keyword">let</span> queue <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> m <span class="token operator">*</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">// 入度为0</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>inDeg<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
      <span class="token punctuation">}</span>

      <span class="token comment">// queue.push(x)</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">while</span> <span class="token punctuation">(</span>queue<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> m <span class="token operator">=</span> queue<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
      queue<span class="token punctuation">.</span><span class="token function">shift</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

      <span class="token comment">// 它的出边(入度为0的)入队</span>
      edges<span class="token punctuation">[</span>m<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">forEach</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token parameter">item</span><span class="token punctuation">)</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
        inDeg<span class="token punctuation">[</span>item<span class="token punctuation">]</span><span class="token operator">--</span><span class="token punctuation">;</span>
        dist<span class="token punctuation">[</span>item<span class="token punctuation">]</span> <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>dist<span class="token punctuation">[</span>item<span class="token punctuation">]</span><span class="token punctuation">,</span> dist<span class="token punctuation">[</span>m<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>inDeg<span class="token punctuation">[</span>item<span class="token punctuation">]</span> <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
          queue<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>item<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
      <span class="token punctuation">}</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
  <span class="token punctuation">}</span><span class="token punctuation">;</span>

  <span class="token function">tpSort</span><span class="token punctuation">(</span><span class="token punctuation">)</span>

<span class="token comment">//   console.log(dist);</span>

  <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token number">0</span>
  <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>dist<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
      res<span class="token operator">=</span>Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>res<span class="token punctuation">,</span>dist<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
  <span class="token punctuation">}</span>

  <span class="token keyword">return</span> res
<span class="token punctuation">}</span><span class="token punctuation">;</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br><span class="line-number">84</span><br><span class="line-number">85</span><br><span class="line-number">86</span><br><span class="line-number">87</span><br><span class="line-number">88</span><br><span class="line-number">89</span><br><span class="line-number">90</span><br><span class="line-number">91</span><br><span class="line-number">92</span><br><span class="line-number">93</span><br><span class="line-number">94</span><br><span class="line-number">95</span><br><span class="line-number">96</span><br><span class="line-number">97</span><br><span class="line-number">98</span><br><span class="line-number">99</span><br><span class="line-number">100</span><br></div></div></div></div>  <div class="page-edit"><div class="edit-link"><a href="https://github.com/linxin1123/vuepress-blog/edit/master/docs/07.算法/41.算法训练营/13.深度-广度搜索-状态空间-cnblog.md" target="_blank" rel="noopener noreferrer">编辑</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----> <div class="last-updated"><span class="prefix">上次更新:</span> <span class="time">2023/02/17, 11:29:32</span></div></div> <div class="page-nav-wapper"><div class="page-nav-centre-wrap"><a href="/pages/1cde21/" class="page-nav-centre page-nav-centre-prev"><div class="tooltip">递归-分治</div></a> <a href="/pages/6789f3/" class="page-nav-centre page-nav-centre-next"><div class="tooltip">动态规划(一)</div></a></div> <div class="page-nav"><p class="inner"><span class="prev">
        ←
        <a href="/pages/1cde21/" class="prev">递归-分治</a></span> <span class="next"><a href="/pages/6789f3/">动态规划(一)</a>→
      </span></p></div></div></div> <div class="article-list"><div class="article-title"><a href="/archives/" class="iconfont icon-bi">最近更新</a></div> <div class="article-wrapper"><dl><dd>01</dd> <dt><a href="/pages/0b785d/"><div>
            Vuex
            <!----></div></a> <span class="date">03-14</span></dt></dl><dl><dd>02</dd> <dt><a href="/pages/c59cc0/"><div>
            Vue响应式原理
            <!----></div></a> <span class="date">03-14</span></dt></dl><dl><dd>03</dd> <dt><a href="/pages/83cc7a/"><div>
            Vue虚拟DOM-cnblog
            <!----></div></a> <span class="date">03-14</span></dt></dl> <dl><dd></dd> <dt><a href="/archives/" class="more">更多文章&gt;</a></dt></dl></div></div></main></div> <div class="footer"><div class="icons"><a href="3010733382@qq.com" title="发邮件" target="_blank" class="iconfont icon-youjian"></a><a href="https://github.com/linxin1123" title="GitHub" target="_blank" class="iconfont icon-github"></a><a href="https://music.163.com/#/playlist?id=755597173" title="听音乐" target="_blank" class="iconfont icon-erji"></a></div> 
  Theme by
  <a href="https://github.com/xugaoyi/vuepress-theme-vdoing" target="_blank" title="本站主题">Vdoing</a> 
    | Copyright © 2022-2023
    <span>lingxin | <a href="https://github.com/linxin1123/vuepress-blog/blob/master/LICENSE" target="_blank">MIT License</a></span></div> <div class="buttons"><div title="返回顶部" class="button blur go-to-top iconfont icon-fanhuidingbu" style="display:none;"></div> <div title="去评论" class="button blur go-to-comment iconfont icon-pinglun" style="display:none;"></div> <div title="主题模式" class="button blur theme-mode-but iconfont icon-zhuti"><ul class="select-box" style="display:none;"><li class="iconfont icon-zidong">
          跟随系统
        </li><li class="iconfont icon-rijianmoshi">
          浅色模式
        </li><li class="iconfont icon-yejianmoshi">
          深色模式
        </li><li class="iconfont icon-yuedu">
          阅读模式
        </li></ul></div></div> <!----> <!----> <!----></div><div class="global-ui"><div></div></div></div>
    <script src="/assets/js/app.57550e13.js" defer></script><script src="/assets/js/2.f014c35f.js" defer></script><script src="/assets/js/111.b092af6d.js" defer></script>
  </body>
</html>
